题目大意
在一个数组（存在重复值）中寻找和为特定值的组合。+
注意点：
所有数字都是正数
组合中的数字要按照从小到大的顺序
原数组中的数字只可以出现一次
结果集中不能够有重复的组合
解题思路
这道题和 Combination Sum 极其相似，主要的区别是Combination Sum中的元素是没有重复的，且每个元素可以使用无限次；而这题中的元素是有重复的，每个元素最多只能使用一次。
代码
更改上一题代码：
- 将candidates[i:]变为candidates[i+1:]
- 再加入flag让后面不必要的累加提前结束（上一题也适用，后来想到的）
- 最后结果有重复，去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not candidates:
return []
candidates.sort()
result = []
self.combination(candidates, target, [], result)
new_result = []
for res in result:
if res not in new_result:
new_result.append(res)
# print new_result
return new_result
def combination(self, candidates, target, current, result):
# print 'candidates', candidates
if current:
# print 'current:', current
s = sum(current)
else:
s = 0
if s > target:
return 1 # 从这里结束匹配不了的循环
elif s == target:
# print 'result:', current
result.append(current)
return 1
else:
for i, v in enumerate(candidates):
# print i, v
flag = self.combination(candidates[i+1:], target, current + [v], result)
if flag == 1:
break
总结
事后在想能不能直接用set存储，这样就不用去重了，但是应该不行，因为set的key不能使可变对象，而慢慢累加的list是不能用tuple来代替存储的。